/**
 * @program: LeetCode
 * @description: LeetCode : 236. 二叉树的最近公共祖先
 * @author: WXY
 * @create: 2023-01-17 20:41
 * @Version 1.0
 **/
public class Num236_lowestCommonAncestor {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == q || root == p)return root;

        TreeNode left = lowestCommonAncestor1(root.left, p, q);
        TreeNode right = lowestCommonAncestor1(root.right, p, q);
        if (left == null && right == null) {
            return null;
        } else if (left != null && right == null) {
            return left;
        } else if (left == null && right != null) {
            return right;
        } else {
            return root;
        }
    }

    public class Info{
        boolean isFindO1;
        boolean isFindO2;
        TreeNode ans;

        public Info(boolean isFindO1, boolean isFindO2, TreeNode ans) {
            this.isFindO1 = isFindO1;
            this.isFindO2 = isFindO2;
            this.ans = ans;
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode O1, TreeNode O2) {
        return process(root, O1, O2).ans;
    }

    private Info process(TreeNode root, TreeNode o1, TreeNode o2) {
        if (root == null) return new Info(false, false, null);
        Info leftInfo = process(root.left, o1, o2);
        Info rifhtInfo = process(root.right, o1, o2);
        boolean isFindO1 = root == o1 || leftInfo.isFindO1 || rifhtInfo.isFindO1;
        boolean isFindO2 = root == o2 || leftInfo.isFindO2 || rifhtInfo.isFindO2;
        TreeNode ans = null;

        if (isFindO2 && isFindO1) {
            if (ans == null) {
                ans = leftInfo.ans == null ? null : leftInfo.ans;
            }
            if (ans == null) {
                ans = rifhtInfo.ans == null ? null : rifhtInfo.ans;
            }
            if (ans == null ) {
                ans = root;
            }
        }

        return new Info(isFindO1, isFindO2, ans);
    }
}
